Day2 Leetcode Array系列----Container With Most Water

本次題目 Container With Most Water by Ruby

我們可以在箱子中每個固定單位樹立隔板，但只能立兩個隔板，在不同位置樹立的隔板高度都有所不同，在這些限制下算出能夠容納最大水量

Input: [1,8,6,2,5,4,8,3,7] //不同位置擋板的高度
Output: 49

思考路線一

1. 雙迴圈去取值，大迴圈就像是左手，抓著一個數字，小迴圈就像右手，一直拿數字過來比較
2. 取到的兩個數字再取最小值當作高度
3. 利用大迴圈產生的i與小迴圈產生的j，相減取絕對值當作長度
4. 高度乘長度得到面積
5. 比較每次面積的值，保留大的

Coding Time

先準備好隔板高度 (數字陣列) ，迴圈起始值 (start)，迴圈終止值 (bottom) ， 水的容量 (higher_volumn) ，

input= [1,8,6,2,5,4,8,3,7]

def max_water_volumn(input)
    start = 0
    bottom = input.length-1
    higher_volumn = 0
end 

大小迴圈，因為是要算面積，所以隔板不可能在同樣的位置，我改變了小迴圈的起始值，讓小迴圈取值比大迴圈前面

def max_water_volumn(input)
    start = 0
    bottom = input.length-1
    higher_volumn = 0

    for i in [*start..bottom]
        new = start + 1
        
        for j in [*new..bottom]
            
        end 
    end
    higher_volumn
end 
p max_water_volumn(input)

從數列中取兩個數找最小值，用i與j得到長度，算出容量

def max_water_volumn(input)
    start = 0
    bottom = input.length-1
    higher_volumn = 0

    for i in [*start..bottom]
        new = start + 1
        
        for j in [*new..bottom]
            height = [input[i],input[j]].min
            length =  (j-i).abs
            now_volumn = length*height

        end 
    end
    higher_volumn
end 

最後把每次算出的容量與目前最大容量相比，如果目前容量大，就把最大容量改成目前容量

完整的code

input= [1,8,6,2,5,4,8,3,7]

def max_water_volumn(input)
    start = 0
    bottom = input.length-1
    higher_volumn = 0

    for i in [*start..bottom]
        new = start + 1
        
        for j in [*new..bottom]
            height = [input[i],input[j]].min
            length =  (j-i).abs
            now_volumn = length*height

            if higher_volumn <=  now_volumn
                higher_volumn = now_volumn
            end
        end 
    end
    higher_volumn
end 
p max_water_volumn(input)

result 49

思考路線--作者

1. 把左邊擋板與右邊擋板當作兩個箭頭看待
2. 如果左邊擋板高度比較低，就把左邊擋板設為高度
3. 左邊的擋板就換成靠右一個單位的
4. 如果右邊擋板高度比較低，就把右邊擋板設為高度
5. 右邊擋版就換成靠左一個單位的
6. 兩個擋版之間的長度就從橫軸座標取得
7. 記錄每次計算容量，把最大值保留

Coding Time

def max_area(heights = [])
  max, start_at, end_at = [0, 0, heights.length - 1]
  while start_at < end_at
    width = end_at - start_at
    high = 0

    if heights[start_at] < heights[end_at]
      high = heights[start_at]
      start_at += 1
    else
      high = heights[end_at]
      end_at -= 1
    end

    temp = width * high
    max = temp if temp > max
  end

  max
end

作者利用 pattern matching 的方式指派變數，max(最大容量)先指派為0，start_at(左側擋版)的箭頭設定0，end_at(右側擋版)的箭頭設定陣列長度-1

設一個while迴圈，當 start_at 比 end_at 就繼續做

寬度就是用 end_at 扣掉 start_at，座標頭尾相扣得長度

做個 if 判斷， 把 start_at 與 end_at 當作索引 (index) 去取值，比較取出來的值大小，用 start_at 取出來的值比較小的話，就用它當作高度， start_at 就 +1 向右移動，反之一樣

最後計算容量，比較每次計算後的大小，把大的保留

結論

作者大大不愧是大大，真是個聰明的想法

今天到此為止，有任何問題請在下方留言或透過email、GitHub聯絡我，感謝閱讀

Daily kitty